package Week6.J0522;

import java.util.ArrayList;
import java.util.Arrays;

public class 字符串的排列_xv {
    boolean[] vis = new boolean[15];
    StringBuffer sbr = new StringBuffer();
    ArrayList<String> ret = new ArrayList<>();
    char[] s;
    int n;

    public ArrayList<String> Permutation(String str) {
        n = str.length();
        s = str.toCharArray();
        Arrays.sort(s);

        dfs(0);
        return ret;
    }

    private void dfs(int pos) {
        if (pos == n) {
            ret.add(sbr.toString());
            return;
        }
        // 填pos位置
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            if (i > 0 && s[i] == s[i - 1] && !vis[i]) continue;

            sbr.append(s[i]);
            vis[i] = true;
            dfs(pos + 1);
            // 恢复现场, 以便重新排列组合
            vis[i] = false;
            sbr.deleteCharAt(sbr.length() - 1);
        }
    }
}
